Question I (a)

queue = [A]
next = A; queue = [B,C]
next = B; queue = [C,I,D,E]
next = C; queue = [I,D,E,F,G]
next = I -> STOP

There are 4 iterations needed to find the Node I in minimum.

Question I (b)



In [1]:

    
grapha = {"A":["B", "C"], 
            "B":["D", "I", "E"], 
            "C":["G", "F"], 
            "D":["E","H"], 
            "E":["I"], 
            "F":["G","A"], 
            "H":[], 
            "I":["F"], 
            "G":[]}



In [2]:

    
def dfs(connects, start, searched):
    """looks if a searched node is in a graph.
    connects: dictionary of arrays,the possible paths
    star: node to start looking for the searched node"""
    lifo = [start]
    visited = set()
    while lifo:
        print(lifo)
        vertex = lifo.pop()
        if vertex == searched:
            return "vertex found!"
        if not vertex in visited:
            lifo += connects[vertex]
            visited.add(vertex)
    return("not found")



In [3]:

    
dfs(grapha,"A","I")









    



['A']
['B', 'C']
['B', 'G', 'F']
['B', 'G', 'G', 'A']
['B', 'G', 'G']
['B', 'G']
['B']
['D', 'I', 'E']
['D', 'I', 'I']






    Out[3]:





'vertex found!'

Minimal steps:

queue = [A]
next = A; queue = [B,C]
next = B; queue = [I,D,E,C]
next = I -> STOP

There are 3 iterations needed to find node I in minimum.

Question II (a)



In [4]:

    
import pandas as pd

adjacency = pd.DataFrame({'A':[0,1,1,0,0,0,0,0,0],
                          'B':[0,0,0,1,1,0,0,0,1],
                          'C':[0,0,0,0,0,1,1,0,0],
                          'D':[0,0,0,0,1,0,0,1,0],
                          'E':[0,0,0,0,0,0,0,0,1],
                          'F':[1,0,0,0,0,0,1,0,0],                          
                          'G':[0,0,0,0,0,0,0,0,0],
                          'H':[0,0,0,0,0,0,0,0,0],
                          'I':[0,0,0,0,0,1,0,0,0]},
                        index =['A','B','C','D','E','F','G','H','I'])
adjacency = adjacency.T

Question II (b)

A graph is acyclic if it contains not only one cycle and directed if the edges have a direction. This grahp contains a cycle (A->C->F->A) so it is not acyclic but the edges have a directions so it is directed.

Question II (c)

Yes there are Eulerian cycles in the graph. Eulerian cycles use every edge exactly once For Example A->C->F->A or A->B->D->E->I->F->A

Question II (d)

Yes there are Hamiltonian cycles in the graph. Hamiltonian cycles use every node exactly once. For Example A->C->F->A or A->B->D->E->I->F->A

Question II (e)

The concept of cliques is only defined for undirected graphs. If the graph in Fig. 1 would be undirected, ACF, CFG, BDE and BEI would me maximal cliques.

Question II (f)

As the graph contains cycles a topological ordering is only possible by violating some of the edges.

Question III



In [5]:

    
def dfs(matrix, query, start):
    # Return True if the query was found
    if query == start:
        return True
    # Return False if Node is already visited
    elif start not in matrix.index:
        return False
    # Return False if there are not outgoing edges
    elif not 1 in matrix.loc[start].values:
        return False
    # Call the function for all unvisited neighbouring nodes
    else:        
        mask = adjacency.loc[start].values == 1
        neighbours = list(adjacency.loc[start][mask].index)
        matrix = matrix.drop(start)
        found = []
        for n in neighbours:
            found.append(dfs(matrix, query, n))
            if any(found) == True:
                return True 
        if all(found) == False:
            return False



In [6]:

    
dfs(adjacency, 'I', 'A')









    Out[6]:





True



In [7]:

    
dfs(adjacency, 'N', 'A')









    Out[7]:





False